package com.example.demo.shuatiban.zuocheng;

/**
 * @author xujm
 * @version V2.4
 *
 * 现在有司机 2*N 人，
 * 调度中心将司机平均调度到 A，B 两个区域，
 * 第 i 个 司机去 A 收入 income[i][0] 元
 * 第 i 个 司机去 B 收入 income[i][1] 元
 * 问所有方案中司机收入最高的方案，多少钱
 * @since 2.4.0 2022/2/2 13:47
 */
public class Arr_让司机获取的总体收入最高 {



    public static int maxMoney(int [][] income){
        if(income.length % 2 !=0){
            return 0;
        }
        int restA = income.length/2;
        return process(income,0,restA);
    }

    public static int process(int [][] income, int index, int restA){

        if(index == income.length){
            return 0;
        }
        //如果A区域已经满了
        if(restA == 0){
            return income[index][1] + process(income, index+1, restA);
        }
        //如果B区域已经满了
        if(income.length - index ==  restA){
            return income[index][0] + process(income, index+1, restA-1);
        }

        //A B 区域选择最大值
        int pA = income[index][1] + process(income, index+1, restA);
        int pB = income[index][0] + process(income, index+1, restA-1);
        return Math.max(pA,pB);
    }

    // 优化，记忆化搜索 复杂度 O(N) * O(N)


    public static void main(String[] args) {


    }


}
